class Solution {
public:
/*
  // 辅助空间从后向前 O(n) O(n)
    string replaceSpace(string s) {
        int len = s.size();
        if(len < 0) return s;
        // 统计空格
        int spacenum = 0;
        for(int i = 0; i < len; ++i)
            if(s[i] == ' ')  ++spacenum;
        int newlen = 2*spacenum + len;    
        string str(newlen, '0');  // 新空间
        int j = newlen-1;
        while(len > 0){
            --len;
            if(s[len] == ' '){
                str[j--] = '0';
                str[j--] = '2';
                str[j--] = '%';
            }
            else
                str[j--] = s[len]; 
        }
        return str;
    }
*/

/*
  // 优化版 辅助空间
    string replaceSpace(string s) {
        if(s.empty()) return s;
        string str;
        for(int i = 0; i < s.size(); ++i){
            if(s[i] == ' '){  //处理空格
                str += "%20";
            }
            else str += s[i];
        }
        return str;
    }
*/

   // 双指针 O(n) O(1)
    string replaceSpace(string s) {
        int len = s.size();
        // 统计空格个数
        int spaceNum = 0;
        for(auto c : s)
            if(c == ' ') ++spaceNum;
        // 扩容
        s.resize(len + 2*spaceNum);
        int newlen = s.size();
        for(int l = len-1, r = newlen-1; l < r; --l,--r){
            if(s[l] == ' '){
                s[r--] = '0';
                s[r--] = '2';
                s[r] = '%';
            }
            else s[r] = s[l];
        }
        return s;
    }
};